1540. 23 из 5

Можно ли так расставить 5 заданных чисел и знаки арифметических операций (+, -, *), чтобы получилось выражение, значение которого равно 23? Считать, что все три указанные операции имеют одинаковый приоритет и выполняются последовательно слева направо.

Вход. Каждая строка содержит пять натуральных чисел от 1 до 50. Последняя строка содержит пять нулей и не обрабатывается.

Выход. Для каждого теста вывести в отдельной строке слово “Possible”, если можно так расставить числа и знаки указанных арифметических операций, чтобы получилось выражение со значением 23. Если этого сделать не возможно, то вывести “Impossible”.

Пример входа	Пример выхода
1 1 1 1 1 1 2 3 4 5 2 3 5 7 11 0 0 0 0 0	Impossible Possible Possible

РЕШЕНИЕ

комбинаторика – перебор вариантов

Анализ алгоритма

Генерируем все перестановки входных чисел. Для каждой перестановки между числами расставляем все возможные знаки арифметических операций и вычисляем полученные выражения. Если хотя бы одно выражение имеет значение 23, то устанавливаем переменную flag в 1 и заканчиваем обработку текущего теста.

Реализация алгоритма

Входную пятерку чисел храним в целочисленном массиве a. Переменная flag принимает значение 1, если найдено выражение со значением 23, иначе flag = 0.

int a[5], flag;

Функция RunSum вычисляет значение выражения, операнды которого находятся в массиве a. Между операндами вставляются знаки всевозможных операций и вычисляются полученные выражения при помощи техники бектрекинга. Если значение одного из выражений равно 23, то функция возвращает 1, иначе 0.

int RunSum(int Sum, int index)

{

if (index == 5)

if (Sum == 23) return 1; else return 0;

if (RunSum(Sum+a[index],index+1)) return 1;

if (RunSum(Sum-a[index],index+1)) return 1;

if (RunSum(Sum*a[index],index+1)) return 1;

return 0;

}

Основная часть программы. Читаем пятерку чисел в массив a. Запускаем процедуру генерации всех перестановок. Поскольку функция next_permutation генерирует перестановки в лексикографическом порядке, то первой должна быть наименьшая перестановка. Наименьшей будет перестановка, у которой числа образуют неубывающую последовательность. То есть перед генерацией перестановок числа в массиве а следует отсортировать по неубыванию (если этого не сделать, то могут быть рассмотрены не все перестановки).

while(scanf("%d %d %d %d %d",

&a[0],&a[1],&a[2],&a[3],&a[4]),a[0]+a[1]+a[2]+a[3]+a[4])

{

sort(a,a+5);

flag = 0;

do{

Для каждой перестановки запускаем функцию RunSum, которая выясняет, можно ли между числами этой перестановки расставить знаки операций так, чтобы получить значение 23.

if (flag = RunSum(a[0],1)) break;

} while(next_permutation(a,a+5));

Если переменная flag установилась в 1, то выводим “Possible”, иначе выводим “Impossible”.

if (flag) printf("Possible\n"); else printf("Impossible\n");

memset(a,0,sizeof(a));

}